/**
角色可以沿任意角度行进的寻路方式
概念：
parentNode:父节点。
checkPoint：检测点
inPoint: 障碍步入点
outPoint:障碍迈出点
compareList:比较列表。存放比较最短路径时参考的节点。是个二维数组。

寻路步骤：
1、找从目标点直线迈向 起始点时第一个步入障碍的点，作为尝试点 
2、从尝试点 沿左右（垂直）方向各找到第一个迈出障碍的点。（）
3、测试迈出点与目标点之间是否有障碍，如果有，则迈出点可作为当前点的子点，
        否则将迈出点作为尝试点，重复第二步操作，直到找到子点为止。一般可以左右各找到一个子点。
4、比较两个子点，将代价最小的子点做为当前点，另一个点封装成节点放入比较列表中。
5、

如果试探节点的negative为false，则把当前节点加入到比较节点列表compareList，
并对compareList各节点的路径值进行比较，选取路径最短的节点作为当前出发点.
注意point和node的区别，也就是点和节点的区别
 
 */
package com.gamebase.findPath
{
	import flash.display.BitmapData;
	import flash.geom.Point;
	import flash.utils.getTimer;
	
	public class DirectPath
	{
		private var _startPoint:Point = new Point();//起始点
		private var _endPoint:Point = new Point();//目标点
		private var compareList:Array = new Array();//比较节点列表(也叫开放列表)
		private var shortestCompareIndex:int = -1;//比较列表中最短的节点组在比较列表中的下标
		private var shortestCompareLen:Number;//比较列表中最短节点组的最短路径长度；
		private var parentNode:PathNode;//每一次找完子点的时候都要将当前出发节点更新为父节点
		private var shortestChildNode:PathNode;//最短子节点
		public var baffleBitmapData:BitmapData;
		public var stepLen:Number = 5;//步长
		public var m_PathArr:Array;//最终路径 
		
		public function DirectPath(baffleBitmapdata:BitmapData=null)
		{
			baffleBitmapData = baffleBitmapdata;
		}
		
		//检查点是否在通道或障碍物上
		private function hitTestPoint(p:Point,hitObject:BitmapData=null):Boolean
		{
			if(hitObject == null)
				hitObject = baffleBitmapData;
			if(hitObject.getPixel(p.x,p.y)==0)
			{
				return false;
			}
			else
				return true;
		}
		
		//查看两点之间是否有障碍物
		private function isPassPath(p1:Point,p2:Point):Boolean
		{
			var p:Point;
			var mcPoint:Point;
			var len:uint = 0;
			var totalLen:uint = Math.floor(Point.distance(p1,p2)/stepLen);
			var stepX:Number = (p2.x - p1.x)/totalLen;//每迈一个步长的X增量
			var stepY:Number = (p2.y - p1.y)/totalLen;
			while(len<totalLen)
			{
				len+=1;
				p = new Point((p1.x+stepX*len),(p1.y+stepY*len))
				if(hitTestPoint(p))
				{
					return false;
					break;
				}
				
			}
			return true;	
		}
		
		
		//寻找步入障碍物的第一个点
		private function findInPoint(p1:Point,p2:Point):Point
		{
			var p:Point;
			var mcPoint:Point;
			var len:uint = 0;
			var totalLen:uint = Math.floor(Point.distance(p1,p2)/stepLen);
			var stepX:Number = (p2.x - p1.x)/totalLen;//每迈一个步长的X增量
			var stepY:Number = (p2.y - p1.y)/totalLen;
			while(len<totalLen)
			{
				len+=1;
				p = new Point((p1.x+stepX*len),(p1.y+stepY*len))
				if(this.hitTestPoint(p))
				{
					return p;
					break;
				}
				
			}
			return null;
		}
		
		//寻找以direction方向迈出障碍物的第一个点
		private function findOutPoint(p1:Point,direction:Number):Point
		{
			var movedLenght:Number = 0;
			var tempPoint:Point;
			var searchNum:uint = 0;
			while(true)
			{
				searchNum++;
				if(searchNum > 100)
				{
					return null;
					break;
				}
				movedLenght += this.stepLen;
				tempPoint = new Point(p1.x+movedLenght*Math.cos(direction),p1.y-movedLenght*Math.sin(direction))
				if(!hitTestPoint(tempPoint))
				{
					return tempPoint;
					break;
				}
			}
			return null;	
		}
		
		//按顺时针或者逆时针方向找P1点到P2点的障碍切线点.direction为true表示顺时针方向
		private function findTangentPoint(p1:Point,p2:Point,direction:Boolean):Point
		{//
			if(hitTestPoint(p1)) return null;
			
			var targetPoint:Point = p2;
			var inPoint:Point;
			var ang:Number;
			var searchNum:uint = 0;
			while(true)
			{
				searchNum++;
				if(searchNum > 100)
				{
					targetPoint = null;
					break;
				}
				if(targetPoint == null) break;
				inPoint = findInPoint(targetPoint,p1);
				if(inPoint == null)
				{
					break;
				}
				else
				{
					ang = Math.atan2(targetPoint.y-p1.y , targetPoint.x-p1.x);
					ang = (ang<0)?-ang:(2*Math.PI-ang);
					if(direction)
						targetPoint = findOutPoint(inPoint,ang-Math.PI/2);
					else
						targetPoint = findOutPoint(inPoint,ang+Math.PI/2);//?targetPoint会不会为null
				}
				
			}
			return targetPoint;
		}
		
		//找子点启发函数。这是不同A*算法的主要区别
		private function findChildPoints(beginPoint:Point):Array
		{
			var arr:Array = new Array();//子点列表
			var angle:Number;
			var inBafflePoint:Point;
			var outBafflePoint:Point;
			var hasPassBaffle:Boolean = false;//测试到checkPoint与当前点间有障碍
			var findNum:uint = 0;//最大子点搜索次数，该限制是为了防止当前点四周都是障碍时出现死循环
			
			//先判断是否可以从当前点直接走到_startPoint
			if(!findInPoint(beginPoint,_startPoint))
				return [_startPoint];
			var findPoint:Point;
			findPoint = findTangentPoint(beginPoint,_startPoint,true);
			if(findPoint != null) arr.push(findPoint);
			findPoint = findTangentPoint(beginPoint,_startPoint,false);
			if(findPoint != null) arr.push(findPoint);
			return arr;
		}
		
		//从compareList中获取路程最短的节点
		private function getShortestCompareNode():PathNode
		{
			var shortIndex:uint = 0
			var shortLen:Number = compareList[shortIndex][0].totalLen;
			var shortPathNode:PathNode;
			for(var k:uint=1; k<compareList.length; k++)
			{
				if(compareList[k][0].totalLen < shortLen)
				{
					shortLen = compareList[k][0].totalLen;
					shortIndex = k;
				}
			}
			
			shortPathNode = compareList[shortIndex].shift();
			if(compareList[shortIndex].length == 0)
			{
				compareList.splice(shortIndex,1);
			}
			return shortPathNode;
		}
		
		//将子点包装成子节点，选取路径最短的子节点,其它子节点组成一个按totalLen升序排列的数组放入比较节点列表
		private function selectChildNode(childPointList:Array):PathNode
		{
			var selectNode:PathNode;
			var childNodes:Array = new Array();
			var i:uint = 0;
			var childNode:PathNode = new PathNode();
			var len:Number
			
			while(i<childPointList.length)
			{
				childNode = new PathNode();
				len = Point.distance(childPointList[i] , _startPoint);
				//childNode.nodeName = "p"+childPointList[i].x+"_"+childPointList[i].y;
				childNode.point = childPointList[i];
				childNode.passPoints = parentNode.passPoints.concat(childNode.point);
				childNode.lessLen = len;
				childNode.passLen = parentNode.passLen + Point.distance(parentNode.point,childNode.point);
				childNode.totalLen = childNode.lessLen + childNode.passLen;
				childNode.negative = false;//？
				childNodes.push(childNode);
				i++;
			}
			//childNodes.splice(childNodes.indexOf(selectNode),1);
			
			//将子节点按路径长度升序排列，然后放入比较列表
			childNodes.sortOn("totalLen" , Array.NUMERIC);
			if(compareList.length == 0)
			{
				selectNode = childNodes.shift();
				if(childNodes.length > 0)
				{
					compareList.push(childNodes);
					shortestCompareIndex = 0;
					shortestCompareLen = childNodes[0].totalLen;
				}
			}
			else if(childNodes[0].totalLen < shortestCompareLen)
			{
				selectNode = childNodes.shift();
				if(childNodes.length > 0)
				{
					compareList.push(childNodes);
					if(childNodes[0].totalLen < shortestCompareLen)
					{
						shortestCompareLen = childNodes[0].totalLen;
						shortestCompareIndex = compareList.length-1;
					}
				}
			}
			else if(childNodes[0].totalLen >= shortestCompareLen)
			{
				selectNode = compareList[shortestCompareIndex].shift();
				if(compareList[shortestCompareIndex].length == 0) compareList.splice(shortestCompareIndex,1);
				compareList.push(childNodes);
				//重新寻找最短节点组
				shortestCompareIndex = 0;
				shortestCompareLen = compareList[0][0].totalLen;
				i = 1;
				while(i<compareList.length)
				{
					if(compareList[i][0].totalLen < shortestCompareLen)
					{
						shortestCompareLen = compareList[i][0].totalLen;
						shortestCompareIndex = i;
					}
					i++;
				}		
			}
			return selectNode;
		}
		
		//优化寻路结果
		private function reSelectPath(arr:Array):Array
		{//过滤掉可以绕过的顶点
			var j:uint = arr.length-2;
			while(j>0)
			{
				if( !findInPoint(arr[0],arr[j]) )
				{
					arr.splice(1,(j-1));
					break;
				}
				j--;
			}
			
			//转换成二维数组
			j = arr.length;
			while(j > 0)
			{
				arr.splice((j-1),1,[arr[j-1].x,arr[j-1].y])
				j--;
			}
			return arr;
		}
		
		//开始搜索路径
		public function findPassPath(startPoint:Point,endPoint:Point):Array
		{
			var costTime:Number = flash.utils.getTimer();
			//如果可以直接通向终点，则返回起始点和终点
			if(!findInPoint(startPoint,endPoint))
			{
				m_PathArr = [[endPoint.x,endPoint.y],[startPoint.x,startPoint.y]];
//				trace("寻路耗时："+(flash.utils.getTimer()-costTime)+"毫秒");
				return m_PathArr;
			}
				
				
			_startPoint = startPoint;
			_endPoint = endPoint;
			compareList.length = 0;
			
			var childPoints:Array = new Array();//当前节点的子点列表
			var searchNum:uint = 0;//当前搜索次数
			//将目标点设置成父节点
			parentNode = new PathNode();
			parentNode.point = _endPoint;
			parentNode.passPoints.push(_endPoint);
			parentNode.lessLen = Point.distance(_endPoint , _startPoint);
			parentNode.passLen = 0;
			parentNode.totalLen = parentNode.lessLen + parentNode.passLen;
			
			
			childPoints = findChildPoints(_endPoint);
			if(childPoints.length>0)
				shortestChildNode = selectChildNode(childPoints);
			else//如果角色周围都是障碍物，则返回空.
			{
				m_PathArr=[];
				trace("角色周围没有可行走区域");
				return m_PathArr;
			}
				 
			//
			while(searchNum < 1000)//100 是经验值
			{trace("----searchNum:"+searchNum)
				parentNode = shortestChildNode;
				childPoints = findChildPoints(shortestChildNode.point);
				if(childPoints.length>0)
				{
					shortestChildNode = selectChildNode(childPoints);
					if(shortestChildNode.point.equals(_startPoint))//找到起始点_startPoint
					{
						m_PathArr = reSelectPath(shortestChildNode.passPoints);
//						trace("寻路耗时："+(flash.utils.getTimer()-costTime)+"毫秒");
						return m_PathArr;
						break;
					}
					//节点的negative属性暂时保留做它用
//					if(shortestChildNode.negative)
//					{
//						if(compareList.length > 0)
//						{
//							compareList[compareList.length -1].unshift(shortestChildNode);
//							shortestChildNode = getShortestCompareNode();
//						}
//						searchNum++;
//						continue;
//					}
				}
				else if(compareList.length >0)//如果当前节点是死节点，并且比较列表有元素，则重新从比较列表中获取最短路径节点为当前点
				{//从比较列表中重新获取路径最短的节点
					trace("--没有字点，从比较列表获取")
					shortestChildNode = getShortestCompareNode();
					searchNum++;
					continue;
				}
				else
				{trace("死路一条")
					break;
				}
				
				searchNum++;
			}
			m_PathArr = reSelectPath(shortestChildNode.passPoints);
			//trace("寻路耗时："+(flash.utils.getTimer()-costTime)+"毫秒");
			return m_PathArr;
		}

	}
}